/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-06-02
 * Time: 22:50
 */

public class Solution {
    // 动态规划
    public int nthUglyNumber(int n) {
        int[] dp = new int[n];
//         三个指针分别表示对应下标的值
//         以其中一个为例, p2 表示使得 dp[p2] * 2 大于前一个丑数的最小的下标
//         也就是说 dp[p2 -1] * 2 就小于前一个丑数, 不符合条件
        int p2 = 0;
        int p3 = 0;
        int p5 = 0;
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            int v2 = dp[p2] * 2;
            int v3 = dp[p3] * 3;
            int v5 = dp[p5] * 5;
//             怎么能保证三个数都大于前一个抽数呢
//             因为前一个抽数是从三个中选出来的最小的那个, 选出来之后最小的那个也变大了, 所以都大于
            dp[i] = Math.min(Math.min(v2, v3), v5);
//             又怎么保证下标最小的的呢
//             因为我们的下标都是被选中之后才移动一格, 这样就保证了最小
            if (dp[i] == v2) {
                p2++;
            }
            if (dp[i] == v3) {
                p3++;
            }
            if (dp[i] == v5) {
                p5++;
            }
        }
        return dp[n-1];
    }
}
